using System;
using System.Collections;
using System.Collections.Generic;

namespace nToolbox.Collections
{
    /// <summary>
    /// Bag is a collection that counts the number of times an item has been added to the collection.
    /// This works best with items that are not mutable as all instances of an item actually reference
    /// the same instance.  Thus, changing one instance will change all instances of the same item.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class Bag<T> : ICollection<T>
    {
        private readonly IDictionary<T, int> bag;
        int count = 0;
        
        #region Constructors
        /// <summary>
        /// Default constructor using a Dictionary as the backing store.
        /// </summary>
        public Bag()
        {
            bag = new Dictionary<T, int>();
        }

        /// <summary>
        /// Constructor using the provided IDictionary as the backing storage.  This allows for easily changing
        /// the initial capacity, equality comparator, or even turning this into a SortedBag by using a SortedDictionary.
        /// </summary>
        public Bag( IDictionary<T, int> dictionary )
        {
            bag = dictionary;
            foreach ( int i in bag.Values )
            {
                count += i;
            }
        }

        #endregion Constructors

        #region ICollection<T> Members

        /// <summary>
        /// Obtain a count of all items in the bag.
        /// </summary>
        public int Count
        {
            get { return count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Add an item to the bag.
        /// </summary>
        public void Add( T item )
        {
            Add( item, 1 );
        }

        /// <summary>
        /// Remove all instances of all items from the Bag.
        /// </summary>
        public void Clear()
        {
            bag.Clear();
            count = 0;
        }

        /// <summary>
        /// Return true if at least one instance of item is in the bag.
        /// </summary>
        public bool Contains( T item )
        {
            return bag.ContainsKey( item );
        }

        /// <summary>
        /// Copy all copies of all elements to the array.
        /// </summary>
        public void CopyTo( T[] array, int arrayIndex )
        {
            if ( array.Length < arrayIndex + count )
            {
                throw new IndexOutOfRangeException( "Array is not long enough to hold all Bag elements." );
            }
            int index = arrayIndex;
            foreach ( KeyValuePair<T, int> pair in bag )
            {
                for ( int i = 0; i < pair.Value; i++ )
                {
                    array[index] = pair.Key;
                    index++;
                }
            }
        }

        /// <summary>
        /// Removes one instance of the item.  Returns true if an item is actually removed.
        /// </summary>
        public bool Remove( T item )
        {
            return Remove( item, 1 );
        }

        #endregion

        #region IEnumerable<T> Members

        /// <summary>
        /// Enumerate through all instances of all items in the bag.
        /// </summary>
        public IEnumerator<T> GetEnumerator()
        {
            return Enumerate().GetEnumerator();
        }

        private IEnumerable<T> Enumerate()
        {
            foreach ( KeyValuePair<T, int> pair in bag )
            {
                for ( int i = 0; i < pair.Value; i++ )
                {
                    yield return pair.Key;
                }
            }
            yield break;
        }
        #endregion

        #region IEnumerable Members

        /// <summary>
        /// Enumerate through all instances of all items in the bag.
        /// </summary>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return Enumerate().GetEnumerator();
        }

        #endregion

        #region New Bag members

        /// <summary>
        /// Get the number of unique items in the Bag.
        /// </summary>
        public int UniqueCount { get { return bag.Count; } } 

        /// <summary>
        /// Add an item copies number of times to the bag.
        /// </summary>
        public void Add( T item, int copies )
        {
            if ( bag.ContainsKey( item ) )
            {
                bag[item] += copies;
            }
            else
            {
                bag.Add( item, copies );
            }
            count += copies;
        }

        /// <summary>
        /// Adds a collection of items to the bag.
        /// </summary>
        public void AddRange( IEnumerable<T> items )
        {
            AddRange( items, 1 );
        }

        /// <summary>
        /// Add the specified number of copies of each item to the bag.
        /// </summary>
        public void AddRange( IEnumerable<T> items, int copies )
        {
            foreach ( T item in items )
            {
                Add( item, copies );
            }
        }

        /// <summary>
        /// Remove at most copies instances of item.  Return true if any items are removed.
        /// </summary>
        public bool Remove( T item, int copies )
        {
            if ( bag.ContainsKey( item ) )
            {
                int orig = bag[item];
                if ( orig <= copies )
                {
                    bag.Remove( item );
                }
                else
                {
                    bag[item] -= copies;
                }
                count -= Math.Min( orig, copies );
                return true;
            }
            return false;
        }

        /// <summary>
        /// Remove all instances of an item.  Return true if any items were removed.
        /// </summary>
        public bool RemoveAll( T item )
        {
            if ( bag.ContainsKey( item ) )
            {
                return Remove( item, Int32.MaxValue );
            }
            return false;
        }

        /// <summary>
        /// Get the count of an item in the Bag.
        /// </summary>
        public int GetCount( T item )
        {
            if ( bag.ContainsKey( item ) )
            {
                return bag[item];
            }
            return 0;
        }

        /// <summary>
        /// Get a list of all items in the bag.
        /// </summary>
        public List<T> ToList()
        {
            List<T> list = new List<T>();
            foreach ( KeyValuePair<T, int> pair in bag )
            {
                for ( int i = 0; i < pair.Value; i++ )
                {
                    list.Add( pair.Key );
                }
            }
            return list;
        }

        /// <summary>
        /// Get a list of only one of each item in the bag.
        /// </summary>
        public List<T> ToUniqueList()
        {
            List<T> list = new List<T>();

            list.AddRange( bag.Keys );
            return list;
        }

        /// <summary>
        /// Get a collection of the unique values in the Bag.
        /// </summary>
        public IEnumerable<T> UniqueValues()
        {
            foreach ( KeyValuePair<T, int> pair in bag )
            {
                yield return pair.Key;
            }
            yield break;
        }

        private Random random = new Random();

        public void SeedRandom( int seed )
        {
            random = new Random( seed );
        }

        /// <summary>
        /// Get a random item from the Bag, optionally removing the item.  If the
        /// Bag is empty, this will return the default value of T.
        /// </summary>
        public T GetRandomItem( bool remove )
        {
            if ( Count <= 0 )
            {
                return default( T );
            }
            int rand = random.Next( count );
            T item = default( T );
            foreach ( KeyValuePair<T, int> pair in bag )
            {
                rand -= pair.Value;
                if ( rand <= 0 )
                {
                    item = pair.Key;
                    break;
                }
            }
            if ( remove )
            {
                Remove( item );
            }
            return item;
        }

        #endregion New Bag members

    }
}
